package basic.study.wantOffer.chapter5;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * @ClassName Problem40
 * @Description 最小的K个数  1.快拍   2.最大堆
 * @Company inspur
 * @Author Kevin
 * @Date 2020/5/23 16:28
 * @Version 1.0
 */
public class Problem40 {
    /**
     * 方法1：采用partition()
     */
    public ArrayList<Integer> GetLeastNumbers_Solution1(int [] input, int k) {
        ArrayList<Integer> leastNumbers = new ArrayList<Integer>();
        while(input==null || k<=0 || k>input.length)
            return leastNumbers;
        int start=0;
        int end=input.length-1;
        int index=partition(input,start,end);
        while(index!=k-1){
            if(index<k-1){
                start=index+1;
                index=partition(input,start,end);
            }else{
                end=index-1;
                index=partition(input,start,end);
            }
        }
        for(int i=0;i<k;i++){
            leastNumbers.add(input[i]);
        }
        return leastNumbers;
    }

    private int partition(int[] arr, int start,int end){
        int pivotKey=arr[start];
        while(start<end){
            while(start<end && arr[end]>=pivotKey)
                end--;
            swap(arr,start,end);
            while(start<end && arr[start]<=pivotKey)
                start++;
            swap(arr,start,end);
        }
        return start;
    }
    private static void swap(int[] arr, int i, int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    //基于堆的容器
    public static int findKthLargest(int[] nums, int k) {
        buildHeap(nums, k);

        for (int i = k; i < nums.length; i++) {
            if (nums[i] < nums[0]) continue;
            swap(nums, i, 0);
            heapify(nums, k, 0);
        }
        return nums[0];
    }

    private static void buildHeap(int[] nums, int k) {
        for (int i  = (k-1)/2; i >= 0; i--) {
            heapify(nums, k, i);
        }
    }


    public static void heapify(int[] arr, int k, int i) {
        int minPos = i;
        while (true) {
            if (2 * i + 1 < k && arr[2 * i + 1] < arr[i]) minPos = 2 * i + 1;
            if (2 * i + 2 < k && arr[2 * i + 2] < arr[minPos]) minPos = 2 * i + 2;
            if (i == minPos) break;
            //若子节点比父节点小，进行交换
            swap(arr, i, minPos);
            i = minPos;
        }
    }


    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(input==null || input.length<k || k<=0)
            return list;
        PriorityQueue<Integer> heap = new PriorityQueue<>(k,(i1, i2)->(i2-i1));
        for(int i=0; i<input.length; i++){
            if(heap.size()<k){
                heap.offer(input[i]);
            }else if(heap.peek()>input[i]){
                heap.poll();
                heap.offer(input[i]);
            }
        }
        for(int i: heap)
            list.add(i);
        return list;
    }

}
